//
// Created by Administrator on 2020/10/28.
//

#ifndef GRAPH_BASIC_SPARSEGRAPH_H
#define GRAPH_BASIC_SPARSEGRAPH_H
#include <iostream>
#include <vector>
#include <cassert>
using namespace  std;

class SparseGraph{
private:
    int n, m;
    bool directed;
    vector<vector<int>> g;
public:
    SparseGraph(int n, bool directed){
        this->n = n;
        this->m = 0;
        this->directed = directed;
        for(int i = 0; i < n; ++i){
            g.push_back(vector<int>());
        }
    }
    ~SparseGraph(){}
    int V(){ return n;}
    int E(){ return m;}
    void addEdge(int v, int w){
        assert(v >= 0 && v < n);
        assert(w >= 0 && w < n);

        g[v].push_back(w);
        if(v != w && !directed) // 处理了自环边，并且防止边数m多加一次
            g[w].push_back(v);
        m++;
    }
    void show(){

        for( int i = 0 ; i < n ; i ++ ){
            cout<<"vertex "<<i<<":\t";
            for( int j = 0 ; j < g[i].size() ; j ++ )
                cout<<g[i][j]<<" ";
            cout<<endl;
        }
    }
    bool hasEdge(int v, int w){
        assert(v >= 0 && v < n);
        assert(w >= 0 && w < n);

        for(int i = 0; i < g[v].size(); ++i){
            if(g[v][i] == w) // 节点v与w相连
                return true;
        }
        return false;
    }
    // 迭代器实现
    class adjIterator{
    private:
        SparseGraph &G;
        int index;
        int v;
    public:
        adjIterator(SparseGraph &graph, int v):G(graph){
            this->v = v;
            this->index = 0; // 与稠密图不同的是，这里的index表示遍历到v的第index个节点，不表示节点index
        }
        int begin(){
            index = 0;  // 如果当前节点无邻边，则end()返回true
            if(G.g[v].size())
                return G.g[v][index];
            return -1;
        }
        int next(){
            index += 1;
            if(index < G.g[v].size())
                return G.g[v][index];
            return -1; // 返回-1说明已经遍历结束，此时index = G.g[v].size()
        }
        bool end(){
            return index >= G.g[v].size();
        }
    };
};
#endif //GRAPH_BASIC_SPARSEGRAPH_H
